package 剑指Offer.easy;

public class 平衡二叉树 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    class Solution {
        public boolean isBalanced(TreeNode root) {
            return recursion(root) != -1;
        }

        private int recursion(TreeNode root) {
            if (root == null) return 0;
            int left = recursion(root.left);
            //剪枝
            if (left == -1) return -1;
            int right = recursion(root.right);
            //剪枝
            if (right == -1) return -1;
            return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
        }
    }
}
